package leetcode.offer_two_special.string;

import java.util.HashMap;

/**
 * @author mazouri
 * @create 2021-09-06 17:56
 */
public class _17_minWindow {
    /**
     * @param s
     * @param t 子串
     * @return
     */
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int count = map.size();
        int start = 0, end = 0, minStart = 0, minEnd = 0;
        int minLen = Integer.MAX_VALUE;
        while (end < s.length() || (count == 0 && end == s.length())) {
            if (count > 0) {
                char endChar = s.charAt(end);
                if (map.containsKey(endChar)) {
                    map.put(endChar, map.get(endChar) - 1);

                    if (map.get(endChar) == 0) count--;
                }

                end++;
            } else {
                if (end - start < minLen) {
                    minLen = end - start;
                    minStart = start;
                    minEnd = end;
                }

                char startChar = s.charAt(start);
                if (map.containsKey(startChar)) {
                    map.put(startChar, map.get(startChar) + 1);
                    //左指针右移 如果发现map中的元素等于1了，就说明窗口里面不全包含子串，需要指针右移
                    if (map.get(startChar) == 1) count++;
                }

                start++;
            }
        }

        return minLen < Integer.MAX_VALUE ? s.substring(minStart, minEnd) : "";
    }

    public static void main(String[] args) {
        System.out.println(new _17_minWindow().minWindow("ADOBECODEBANCD", "ABC"));

        String s = "ADOBECODEBANC";
        System.out.println(s.substring(1, 3));
    }
}